暴力递归

1. 把问题转化为规模缩小了的同类问题的子问题
2. 有明确的不需要继续进行递归的条件(base case)
3. 有当得到了子问题的结果之后的决策过程
4. 不记录每一个子问题的解

动态规划

1. 从暴力递归中来
2. 将每一个子问题的解记录下来，不断重构最优解
3. 最终得到问题的解
4. 把暴力递归的过程，抽象成了状态表达

本质上状态空间的状态转移。

所谓状态转移是指每个阶段的最优状态（对应于子问题的解）可以从之前的某一个或几个阶段的状态中得到，即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解，这个性质叫做最优子结构。而不管之前这个状态是如何得到的，这被称之为无后效性。

关键在于：如何求解递推式！

1. 如何设置状态
2. 如何递推，从上一个状态如何转化到下一个状态
3. 最终达到最优解

背包问题

01背包

题目：

有N件物品和一个空间为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

例如：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，每件物品数量只有一个，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和。

特点：每种物品仅有一件，可以选择放或不放

分析：

只放一件物品价值最大，选取在承重范围内的最大值放进背包

只放两件物品价值最大，两种情况：１，在放一件物品最大后，在剩余承重下再放一件；２，重新选择两件物品。这两种情况谁价值大选谁。

自顶向下分析：

两个变量：物品数i和空间j，

一个所求：背包最大价值。

数组$W[i][j]$表示有i个物品可以选择放入空间为j的背包中的最大价值，注意是选择放入不是全部放入背包

当ｉ＝Ｎ且ｊ＝Ｖ时就是所求。

所以，$W[i][j]$可以由子问题$W[i-1][j]$，即有ｉ－１个物品可选择放入空间为ｊ的背包中的最大价值，加上第ｉ个物品构成。有两种情况：

第一：第ｉ个物品放入背包，$W[i][j]=W[i-1][j-c_i]+w_i$

第二：第ｉ个物品不放入背包，$W[i][j]=W[i-1][j]$

取两者最大值就是i个物品可以选择放入空间为j的背包中的最大价值$W[i][j]$

自底向上求解：

由ｉ＝０，ｊ＝０开始逐步求解$W[i][j]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int knapsack(int *value,int *cost,int n,int v){
    vector<vector<int> > W(n,vector<int>(v,0)); //n行v列二维数组，初始化为０
    int max=0;
    for(int i=0;i<n;++i){ //第ｉ个物品
        for(int j=1;j<v;++j){ //空间
            if(i==0 && j>=cost[i])W[i][j]=value[j];//初始化第一排数据，即只有一个物品时
            if(j<cost[i]){  //书包空间装不下第ｉ个物品时
                W[i][j]=W[i-1][j];
            } else {
                W[i][j]=max(W[i-1][j],W[i-1][j-cost[i]]+value[i]);        
            }          
            max=(W[i][j]>max)W[i][j]:max;    
        }
    }
    return max;
}

时间复杂度：$O(NV)$

空间复杂度：$O(NV)$

空间优化：只需要一个一维数组就可以保存需要的数据。空间复杂度可以优化到$O(V)$

上面的方法是用一个二维数组保存子问题的解（ｉ－１个物品放入空间为ｊ的背包的最大价值）

在做递推的时候只用了ｉ－１行的数据，所以可以使用一个一位数组只保存ｉ－１行的数组。

1
2
3
4
5
6
7
8
9
10
11

int knapack(const vector<int> value,const vector<int> cost,int n,int v){
    vector<int> W(v+1);
    for(int i=0;i<n;++i){ //n个物品，依次增加种类
        for(int j=v;j>=1;--j){　//逆序，
            if(j>=cost[i]){//空间够放第ｉ个物品时，才放入
                W[j]=max(W[j-cost[i]]+value[i],W[j-1]);
            }  
        }
    }
    return W[v];
}

空间ｖ的遍历一定是逆序。这样才能保证$W[j-cost[i]]$不会在ｊ的一次循环内被更新，保证了物品只能使用一次。比如，

完全背包

题目：

有N种物品和一个空间为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包空间，且价值总和最大。

分析：

N种物品无限使用，也就相当于少了一个限制，求空间为Ｖ的背包最大价值是多少。

$W[V]$表示空间为Ｖ的书包的最大价值。

$W(V)=argmax(W(V-c_i)+w_i)$

1
2
3
4
5
6
7
8
9
10

int knapack_comlete(const vector<int> value,const vector<int> cost,int n,int v){
    vector<int> W(v+1);
    for(int i=1;i<=v;++i){ //空间为ｉ时的最大价值
        for(int j=0;j<n;++j){　//逐个物品进行尝试，这保证可以使用无限多次
            if(i<cost[j])continue;
            W[i]=max(W[i-cost[j]]+value[j],W[i-1]);     
        }
    }
    return W[v];
}

多重背包

题目：

有N种物品和一个空间为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包空间，且价值总和最大。

分析：

对于第ｉ个物品，
$$
W[i][j]=max(W[i-1][j],W[i-1][j-kc_i]+kc_i)
$$
其中，$k$的取值范围是$(1,n[i])$．

时间复杂度是$O(V*\sum(n[i]))$

最长公共子序列

题目：

给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

分析：

公共子序列 ： 如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。空序列是任何两个序列的公共子序列。

1. 确定动态规划问题，
2. 寻找ＤＰ数组，一维ｏｒ二维。题目包含两个变量，字符串１和字符串２。
3. 确定递推式。关于字符串的变量一般就是长度。两个字符串的长度变化对最长子序列的结果都有影响。确定$DP[i][j]$表示字符串１中长度为ｉ时与字符串２中长度为ｊ的最长公共子序列的长度。
4. $DP[i][j]$可以由三部分（$DP[i-1][j]，DP[i][j-1]，DP[i-1][j-1]$）递推得到，所以，有

$$
DP[i][j]=max(DP[i-1][j],DP[i][j-1]),if(str1[i]!=str2[j])
$$

$$
DP[i][j]=DP[i-1][j-1]+1,if(str1[i]=str2[j])
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int MaxCommonSeq(string str1,string str2){
    int len1=str1.size();
    int len2=str2.size();
    vector<vector<int> > DP(len1+1,vector<int>(len2+1,0));//+1是为了更好的处理单个字符的情况
    for(int i=1;i<=len1;++i){
        for(int j=1;j<=len2;++j){
            if(str1[i-1]==str2[j-1]){
                DP[i][j]=DP[i-1][j-1]+1;
            } else {
                DP[i][j]=max(DP[i-1][j],DP[i][j-1]);
            }
        }
    }
    return DP[len1][len2];
}